package com.yanceysong.codetop.s51_s60;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class S53_Mid_322_零钱兑换 {
    /**
     * .S53_Mid_322_零钱兑换
     * .<p>
     * .题目链接：<a href="https://leetcode.cn/problems/coin-change/">https://leetcode.cn/problems/coin-change/</a>
     * .<p>
     * .【题目描述】
     * .给定一个包含不同面额硬币的数组 coins，以及一个目标金额 amount。每种硬币数量无限。
     * .求凑成该金额所需的最少硬币个数；若无法凑成，返回 -1。
     * .<p>
     * .【示例】
     * .示例1：coins = [1,2,5], amount = 11 -> 3  (5 + 5 + 1)
     * .示例2：coins = [2], amount = 3 -> -1
     * .示例3：coins = [1], amount = 0 -> 0
     * .<p>
     * .【核心标签】动态规划 / 完全背包 / 记忆化搜索
     * .<p>
     * .【核心思路（自底向上 DP）】
     * .定义：minCoins[x] 表示凑成金额 x 的最少硬币数。
     * .初值：minCoins[0] = 0 （金额为 0 不需要硬币）。
     * .状态转移：对于每个金额 x，枚举每种硬币面值 c：
     * .  若 c <= x 且 minCoins[x - c] 可达，则：
     * .     minCoins[x] = min( minCoins[x], minCoins[x - c] + 1 )
     * .最终答案：minCoins[amount]；如果仍为哨兵值(不可达)，返回 -1。
     * .<p>
     * .【ASCII 过程演示】（coins=[1,2,5], amount=7）
     * .金额 0: 0
     * .金额 1: min(∞, dp[0]+1)=1 -> [1]
     * .金额 2: min(∞, dp[1]+1=2, dp[0]+1=1)=1 -> [2]
     * .金额 3: min(∞, dp[2]+1=2, dp[1]+1=2)=2 -> [1,2] 或 [2,1]
     * .金额 4: min(∞, dp[3]+1=3, dp[2]+1=2)=2 -> [2,2]
     * .金额 5: min(∞, dp[4]+1=3, dp[3]+1=3, dp[0]+1=1)=1 -> [5]
     * .金额 6: min(∞, dp[5]+1=2, dp[4]+1=3, dp[1]+1=2)=2 -> [5,1]
     * .金额 7: min(∞, dp[6]+1=3, dp[5]+1=2, dp[2]+1=2)=2 -> [5,2]
     * .<p>
     * .【关键洞察】
     * .1. 问题是“最少数量”而不是“组合数”，自然想到最短路径或最优子结构 -> DP。
     * .2. 本质是完全背包：物品(硬币)可重复使用，顺序不重要（组合型）。
     * .3. 选择哨兵值 (amount + 1) 表示“不可达”，避免使用 Integer.MAX_VALUE 导致溢出 + 1 问题。
     * .4. 若硬币包含 1，则所有金额可达；若没有 1，需正确返回不可达情况。
     * .5. 记忆化 DFS 与自底向上 DP 皆可；DP 更直观且易于控制复杂度。
     * .<p>
     * .【复杂度分析】
     * .时间复杂度：O(amount * .coins.length)
     * .空间复杂度：O(amount)
     * .<p>
     * .【常见易错点】
     * .- 忘记初始化 dp[0] = 0。
     * .- 使用 Integer.MAX_VALUE 再加 1 可能溢出。
     * .- 忘记判断最终结果是否仍为哨兵值。
     * .- 将问题误解为“排列”导致过度计数。
     */
    public int coinChange(int[] coins, int amount) {
        if (amount == 0) {
            // 直接返回，无需硬币
            return 0;
        }
        if (coins == null || coins.length == 0) {
            // 无硬币，除非 amount==0
            return -1;
        }
        // 哨兵值：表示当前金额尚不可达；最大可能硬币数为 amount（全用面值 1）
        int unreachableFlag = amount + 1;
        int[] minCoins = new int[amount + 1];
        Arrays.fill(minCoins, unreachableFlag);
        minCoins[0] = 0;
        // 外层遍历金额（也可以先遍历硬币，等价，本题不需记录方案）
        for (int currentAmount = 1; currentAmount <= amount; currentAmount++) {
            for (int coinValue : coins) {
                if (coinValue <= currentAmount) {
                    // 如果 currentAmount - coinValue 可达，则尝试更新
                    minCoins[currentAmount] = Math.min(minCoins[currentAmount]
                            , minCoins[currentAmount - coinValue] + 1);
                }
            }
        }
        return minCoins[amount] == unreachableFlag ? -1 : minCoins[amount];
    }

    /**
     * .递归 + 记忆化搜索版本（自顶向下）。可能在大 amount 时性能略低于迭代 DP，但展示另一思路。
     */
    public int coinChangeMemo(int[] coins, int amount) {
        if (amount == 0) return 0;
        if (coins == null || coins.length == 0) return -1;
        Map<Integer, Integer> memo = new HashMap<>();
        return dfs(coins, amount, memo);
    }

    private int dfs(int[] coins, int remain, Map<Integer, Integer> memo) {
        if (remain == 0) return 0;
        if (remain < 0) return -1;
        if (memo.containsKey(remain)) return memo.get(remain);
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int sub = dfs(coins, remain - coin, memo);
            if (sub == -1) continue; // 不可达
            min = Math.min(min, sub + 1);
        }
        int ans = (min == Integer.MAX_VALUE) ? -1 : min;
        memo.put(remain, ans);
        return ans;
    }

    // ===================== 测试辅助方法 =====================

    private static void runCase(int id, int[] coins, int amount, int expected) {
        S53_Mid_322_零钱兑换 solver = new S53_Mid_322_零钱兑换();
        int dpAns = solver.coinChange(coins, amount);
        int memoAns = solver.coinChangeMemo(coins, amount);
        boolean pass = (dpAns == expected) && (memoAns == expected);
        System.out.printf("Case %02d | coins=%s amount=%d | dp=%d memo=%d | expected=%d | %s\n",
                id, Arrays.toString(coins), amount, dpAns, memoAns, expected, pass ? "PASS" : "FAIL");
        assert pass : "测试未通过: case=" + id;
    }

    public static void main(String[] args) {
        System.out.println("=== 零钱兑换测试开始 ===");
        // 题目示例
        runCase(1, new int[]{1, 2, 5}, 11, 3);
        runCase(2, new int[]{2}, 3, -1);
        runCase(3, new int[]{1}, 0, 0);

        // 基础可达/不可达
        runCase(4, new int[]{1, 3, 4}, 6, 2); // 3+3 或 4+1+1 (最优 2)
        runCase(5, new int[]{5, 1, 2, 2}, 7, 2); // 5+2
        runCase(6, new int[]{5, 7, 8}, 1, -1); // 不可达
        runCase(7, new int[]{3, 5, 7}, 0, 0); // amount=0

        // 较大典型（LeetCode 已知测试）
        runCase(8, new int[]{186, 419, 83, 408}, 6249, 20);

        // 非贪心测试（贪心不一定最优）
        runCase(9, new int[]{1, 4, 5}, 8, 2); // 4+4 优于 5+1+1+1

        // 中等金额
        runCase(10, new int[]{1, 2, 5, 10, 20, 50, 100}, 99, 6); // 50+20+20+5+2+2

        // 较大金额性能测试（仅验证 DP 正确，不追求方案）
        runCase(11, new int[]{1, 2, 5}, 1000, 200); // 全用 5

        System.out.println("=== 所有测试完成 ===");
        System.out.println("(提示：启用断言请使用 -ea 参数运行 JVM)");
    }
}
